/**
 * created by lpw
 */
public class TestClass {
    public static void main(String[] args) {
        Node node = createLinked();
//        boolean b = hasCircle(node);
        Node circleFirstNode = circleFirstNode(node);
        System.out.println(circleFirstNode==null?"没有环":circleFirstNode.data);
    }

    /**
     *检测环
     */
    public static boolean hasCircle(Node head){
        if (head ==null ){
            return false;
        }
        Node quick=head.next;
        Node slow=head;
        /**
         * 快慢指针一块走，如果有环，这个循环永远也出不来，一定会存在slow==quick
         * 如果没环，则会走到最后一个节点，跳出循环
         */
        while (quick!=null && quick.next!=null){
            slow=slow.next;
            quick=quick.next.next;
            if (slow==quick){
                return true;
            }
        }
        return false;
    }

    //打印链表
    public static void logNode(Node node){
        Node temp=node;
        while (temp!=null){
            System.out.println(temp.data);
            temp=temp.next;
        }
    }

    //生成链表,建了一个换
    public static Node createLinked(){
        Node node1=new Node("1");
        Node node2=new Node("2");
        Node node3=new Node("3");
        Node node4=new Node("4");
        Node node5=new Node("5");
        Node node6=new Node("6");
        Node node7=new Node("7");
        Node node8=new Node("8");
        Node node9=new Node("9");

        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;
        node7.next=node8;
        node8.next=node9;
        node9.next=node4;
        return node1;
    }

    //使用遍历反转链表
    public static Node linkedReversal(Node oldNode){
        if (oldNode == null) return null;
        Node pre = oldNode;
        Node cur = oldNode.next;
        Node temp;
        while (cur != null) {// 为空，说明到最后了
            temp = cur.next;
            cur.next=pre;// 反转指针域的指向
            // 指针往下移动
            pre = cur;
            cur = temp;
        }
        // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
        oldNode.next=null;
        return pre;
    }

    /**
     * 查找环的入口节点
     *  假定到环的入口节点长度为L1，入口节点到快慢指针相遇点长度为L2，慢节点走了n步，此时有
     *  慢节点：L1+L2+m*环=n
     *  快节点：L1+L2+k*环=2n
     *  可以得出（k-m）*环=n，k-m为整数，n就是环的倍数
     *  所以有 L1+L2=a*环，即L1+L2也是环的倍数
     *  此时慢节点置回头结点，快节点继续往下走，步长改为1，都走L1+L2步，必定会返回现在节点
     *  且L2的长度会是两个节点重合的步分
     *  那么，两个节点相遇的第一个点，其实就是环的入口
     */
    public static Node circleFirstNode(Node head) {
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            //没有环
            return null;
        }

        slow = head;
        while(fast != slow){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

}

class Node {
    String data;
    Node next;

    public Node(String data) {
        this.data = data;
    }
}